Fechar

%0 Thesis
%4 sid.inpe.br/iris@1905/2005/07.26.00.13.38
%2 sid.inpe.br/iris@1905/2005/07.26.00.13.48
%F 3517
%T Algoritmos de programação não linear (Volumes I, II, III, IV, V e VI)
%J x
%D 1975
%8 1974-06-05
%9 Dissertação de Mestrado
%P 1176
%A Coutinho, Artur Aparecido Valério,
%A Mostafe, Mamdouh Mahmoud,
%A Guimarães, Mauro,
%A Simoni, Paulo Ouvera,
%A Rego, Raimundo de Souza,
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%E Lapa, Jair dos Santos (orientador),
%E Ferras, José Eugenio Guisard,
%E Taube Netto, Miguel,
%I INPE
%C São José dos Campos
%K computação aplicada, algoritmos, algorithms.
%X VOL. I: Este volume visa fazer uma apresentação dos demais volumes, que constituem o corpo do trabalho, bem como as condições de utilização de cada um dos algoritmos estudados e programados. Contém ainda uma breve exposição de conceitos matemáticos, necessários compreensão da parte te6rica dos algoritmos. ABSTRACT: This volume is comprised of a summary of the complete work (which follows in five volumes), as well as the conditions necessary for the application of each of the algorithms studied and programmed. It also contains some of the mathematical concepts which are necessary to the understanding of the theory of the algorithms. VOL II: O objetivo deste trabalho é apresentar e discutir em detalhes o Método de Beale para minimizar uma função quadrática, convexa, sujeita a restrições lineares. É exigido do leitor conhecimentos básicos de cálculo e de programação linear. Inicialmente, com a finalidade de dar uma conceituação do algoritmo, apresenta-se um diagrama de funcionamento do algoritmo e um exemplo simples resolvido num gráfico. Em seguida á apresentado o desenvolvimento teórico do algoritmo com as necessárias provas matemáticas. Também é mostrada a convergência do algoritmo. Finalmente, é apresentada, uma codificação em FORTRAN, do algoritmo de Beale para o computador B-6700 da BURROUGRS. Esta codificação é acompanhada de diagramas e exemplos. ABSTRACT: The objective of this work is to discuss in detail Beale's method for minimizing a convex quadratic function, subject to linear constraints. The reader is supposed to have a background in calculus and linear programming. At the beginning, with the purpose of giving a conceptualization of the algorithm, we present a flow diagram of the algorithm and a simple example solved graphically. After this, the theoretical development of the algorithm is presented with the necessary mathematical prooft. The algorithm convergence is also shown. Finally, a computer programme of Beale's algorithm is presented, in FORTRAN for the BORROUGHS B -6700 model. This programe is followed by diagrams and examples. VOL. III: Este volume apresenta o trabalho relativo aos métodos de Barankin e Dorfman e de Frank e Wolfe. Ambos os métodos minimizam uma função quadrática convexa, cujas variáveis são não negativas e sujeitas a um conjunto de desigualdades lineares. São feitas transformações no problema original, baseadas nas condições de otimalidade de Kuhn-Tucker, obtendo-se uma nova função a ser minimizada e um conjunto adicional de restrições. No método de Barankin e Dorfman, são utilizadas técnicas modificadas para programas lineares, a fim de diminuir o valor da nova função objetivo em cada passo. No método de Frank e Wolfe, a nova função objetivo é linearizada em cada passo, sendo minimizada por técnicas de programação linear. Os dois métodos permitem a obtenção de soluções sub-ótimas para o problema. Permitem saber, no primeiro passo, se o problema é inviável, ilimitado ou se possui solução ótima. Apresentamos a conceituação do método, estudo da teoria e aspectos computacionais, para cada método. Acompanha o trabalho a codificação dos algoritmos, em FORTRAN para o computador BURROUGES B-6700, e um roteiro para facilitar a utilização destes algoritmos, contendo a descrição dos parâmetros e a forma de entrada dos dados. ABSTRACT: This volume presents the work relative to the methods of Barankin and Dorfman and of Frank and Wolfe. These methods minimize a convex quadratic function, whose variables are non-negative and subject to a set of linear inequalities. Transformations are made on the original problem, according to Kuhn-Tucker's optimality conditions, resulting in a new function to be minimized and an additional set of constraints. In the method of Barankin and Dorfman, modified techniques for linear programs are used to decrease the value of the new objective function at each step. In the method of Frank and Wolfe, the new objective function is linearized at each step and is minimized by linear programming techniques. Both methods enable us to get sub-optimal solutions for the problem. It is possible to know, at the first step, if the problem is infeasible, unlimited or if it has an optimal solution. We present an intuitive approach, a theoretical study and computational features for each method. Computer programmes for the algorithms (in FORTRAN for the BURROUGHS B-6700 model) and a guide to apply these algorithms, consisting of a description of the parameters and data input format, were added to this work. VOL. IV: Este volume apresenta um trabalho relativo ao método da Projeção do Gradiente de Rosen. Este método maximiza uma Função Côncava Diferençável sujeita a Restrições Lineares. O Método de Rosen é um Método do Gradiente. Sua principal característica é que durante a maximização caminhamos na direção da projeção do gradiente sobre o contorno da região viável, sempre que o ponto pertença a este contorno e o gradiente aponte para fora. Este trabalho consta da Teoria e da Conceituação do Método, Problemas resolvidos graficamente e uma discussão das Regras Computacionais Aplicadas. Ele tem também uma Codificação FORTRAN para o computador BURROUGHS B-6700 com Instruções para o usuário e Fluxogramas. ABSTRACT: This volume presents a work about Rosen's Projection Gradient Method. This Method maximizes a Concave Differentiable Function subject to Linear Constrainsts Rosen's Method is a Gradient Method. It is characterized by following the direction of the gradient projection on the boundary of the feasible domain, whenever the point belongs to this boundary and the gradient points outside the feasible domain. This work contains the Theory and Conceptualization of the Method, Problems solved graphically, and a discussion on the Computation Rules applied. It includes a FORTRAN Programme for the BURROUGHS B-6700 computer, Instructions for the user, and Flow Diagrams. VOL. V: Apresenta-se neste trabalho dois m métodos de minimização de funções de diversas variáveis, sem restrições. Método de Davidon-Fletcher e Powell. Este método, baseado nas idéias de Davidon e idealizado por Fletcher e Powell, é um dos mais eficientes métodos de primeira ordem. As informações obtidas nas iterações já executadas são usadas para montar uma matriz que aproxima a hessiana da função sendo minimizada. Método de Powell. Aplica-se nos casos práticos onde, normalmente, derivadas não são de fácil cálculo. É uma simples variação do método clássico de minimizar uma função de diversas variáveis alterando uma só variável por vez. O método de Powell é considerado o mais eficiente dos métodos de minimização sem calcular derivadas. Teoremas sobre convergência quadrática e estabilidade dos métodos são mostrados. Os dois métodos foram programados em FORTRAN para o computador B-6700. Testes numéricos e detalhes dos programas são incluídos. ABSTRACT: In this work, two different methods for locating an unconstrained minimum of a function of several variables are described. - Davidon - Fletcher and Powell method. This method, based upon the ideas of Davidon and developed by Fletcher and Powell, is one of the most efficient first order methods. The information obtained during the previously made iterations are used in constructing cm approximation of the hessian of the function being minimized. - Powell's method. This method is applicable for the practical cases where, normally, derivatives are not easily calculated. It is a simple variation of the classical method of minimizing a function of several variables by changing one parameter at a time. The method is considered to be the most efficient of all method of minimization without calculating derivatives. Theorems concerning the quadratic convergence and stability of the methods are proved. Computer programmes in FORTRAN for the B-6700 model were prepared for the two methods. Numerical tests and programme details are included. VOL. VI: Este trabalho apresenta o Algoritmo dos Pontos Interiores de Fiacco e McCormick (referência {{[6]),}} que serve para resolver problemas não lineares com restrições em forma de desigualdades passíveis de serem satisfeitas estritamente. Os mais importantes resultados matemáticos relacionados com o algoritmo são apresentados em detalhes. Foi desenvolvida uma codificação em FORTRAN suficientemente detalhada para permitir sua utilização por pessoas não especialistas na área. Como se apresenta, esta codificação se aplica ao computador BURROUGHS-6700. Este algoritmo de Fiacco e McCormick se caracteriza como uma técnica de minimização sequencial e irrestrita. Basicamente o método agrupa tanto as restrições quanto a função objetivo em uma única função que é minimizada irrestritamente diversas vezes, sofrendo entre uma minimização e outra uma pequena alteração em um de seus parâmetros. ABSTRACT: This work presents the interior points algorithm of Piacco and McCormick (reference {{[6]),}} which is applicable to nonlinear programming problems with inequality constraints that must be satisfiable in the inequality form. The most important related mathematical results are discussed in details. A FORTRAN programme, sufficiently detailed to be used by nonspecialists, is presented. The programme as presented, is to be used in the BURROUGHS-6700 computer model. The algorithm of Fiacco and McCormick is characterized as one of the sequential unconstrained minimization techniques. Basically, the method joins both the objective function and the constraints in a single function that is repeatedly minimized with one of its parameters being slightly changed from one minimization to the other.
%@language pt
%3 INPE-596- v. I a VI.pdf


Fechar